package ink.lovejinhu.swardToOffer;

public class Offer_010_II {
    public int numWays(int n) {
        if (n==0){
            return 1;
        }
        if (n==1){
            return 1;
        }
        long[] ints = new long[3]; //滚动数组,越界
        ints[0]=0;
        ints[1]=1;
        ints[2]=1;
        for (int i = 3; i <=n ; i++) {
            long temp=ints[1]+ints[2];
            ints[0]=ints[1];
            ints[1]=ints[2];
            ints[2]=temp%1000000007;
        }

        return (int) ints[2];
    }
}
